{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Last Substring in Lexicographical Order"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lastSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按字典序排在最后的子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，找出它的所有子串并按字典序排列，返回排在最后的那个子串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abab\"\n",
    "<strong>输出：</strong>\"bab\"\n",
    "<strong>解释：</strong>我们可以找出 7 个子串 [\"a\", \"ab\", \"aba\", \"abab\", \"b\", \"ba\", \"bab\"]。按字典序排在最后的子串是 \"bab\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"leetcode\"\n",
    "<strong>输出：</strong>\"tcode\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 4 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 仅含有小写英文字符。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [last-substring-in-lexicographical-order](https://leetcode.cn/problems/last-substring-in-lexicographical-order/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [last-substring-in-lexicographical-order](https://leetcode.cn/problems/last-substring-in-lexicographical-order/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abab\"', '\"leetcode\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "\n",
    "        i = 0\n",
    "        j = 1\n",
    "        k = 0\n",
    "\n",
    "        while j + k < len(s):\n",
    "            if s[i+k] == s[j+k]:\n",
    "                k = k + 1\n",
    "            elif s[i+k] < s[j+k]:\n",
    "                i += k + 1\n",
    "                k = 0\n",
    "                if i >= j:\n",
    "                    j = i + 1\n",
    "            else:\n",
    "                j += k + 1\n",
    "                k = 0\n",
    "        \n",
    "        return s[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        i, j, k = 0, 1, 0\n",
    "        while j + k < len(s):\n",
    "            if s[i + k] == s[j + k]:\n",
    "                k += 1\n",
    "            elif s[i + k] < s[j + k]:\n",
    "                i = i + k + 1\n",
    "                k = 0\n",
    "                if i >= j:\n",
    "                    j = i + 1\n",
    "            else:\n",
    "                j = j + k + 1\n",
    "                k = 0\n",
    "        return s[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        i,j,k = 0,1,0\n",
    "        while j + k < len(s):\n",
    "            if s[i + k] == s[j + k]:\n",
    "                k += 1\n",
    "            elif s[i + k] > s[j + k]:\n",
    "                j += k + 1\n",
    "                k = 0\n",
    "            else:\n",
    "                i += k + 1\n",
    "                k = 0\n",
    "                if i >= j:\n",
    "                    j = i + 1\n",
    "        return s[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        i, j, k = 0, 1, 0\n",
    "        while j + k < len(s):\n",
    "            if s[i + k] == s[j + k]:\n",
    "                k += 1\n",
    "            elif s[i + k] < s[j + k]:\n",
    "                i = i + k + 1\n",
    "                k = 0\n",
    "                if i >= j:\n",
    "                    j = i + 1\n",
    "            else:\n",
    "                j = j + k + 1\n",
    "                k = 0\n",
    "        return s[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        # 贪心，升序排在后面的肯定是相同字母并且长度最长的子字符串\n",
    "        return max(s[i:] for i in range(len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        n = ''\n",
    "        for i in range(len(s)):\n",
    "            n = max(n, s[i:])\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LyndonDecomposition:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    # duval_algorithm\n",
    "    @staticmethod\n",
    "    def solve_by_duval(s):\n",
    "        n, i = len(s), 0\n",
    "        factorization = []\n",
    "        while i < n:\n",
    "            j, k = i + 1, i\n",
    "            while j < n and s[k] <= s[j]:\n",
    "                if s[k] < s[j]:\n",
    "                    k = i\n",
    "                else:\n",
    "                    k += 1\n",
    "                j += 1\n",
    "            while i <= k:\n",
    "                factorization.append(s[i: i + j - k])\n",
    "                i += j - k\n",
    "        return factorization\n",
    "\n",
    "    # smallest_cyclic_string\n",
    "    @staticmethod\n",
    "    def min_cyclic_string(s):\n",
    "        s += s\n",
    "        n = len(s)\n",
    "        i, ans = 0, 0\n",
    "        while i < n // 2:\n",
    "            ans = i\n",
    "            j, k = i + 1, i\n",
    "            while j < n and s[k] <= s[j]:\n",
    "                if s[k] < s[j]:\n",
    "                    k = i\n",
    "                else:\n",
    "                    k += 1\n",
    "                j += 1\n",
    "            while i <= k:\n",
    "                i += j - k\n",
    "        return s[ans: ans + n // 2]\n",
    "\n",
    "    @staticmethod\n",
    "    def min_express(sec):\n",
    "        n = len(sec)\n",
    "        k, i, j = 0, 0, 1\n",
    "        while k < n and i < n and j < n:\n",
    "            if sec[(i + k) % n] == sec[(j + k) % n]:\n",
    "                k += 1\n",
    "            else:\n",
    "                if sec[(i + k) % n] > sec[(j + k) % n]:\n",
    "                    i = i + k + 1\n",
    "                else:\n",
    "                    j = j + k + 1\n",
    "                if i == j:\n",
    "                    i += 1\n",
    "                k = 0\n",
    "        i = i if i < j else j\n",
    "        return i, sec[i:] + sec[:i]\n",
    "\n",
    "    @staticmethod\n",
    "    def max_express(sec):\n",
    "        n = len(sec)\n",
    "        k, i, j = 0, 0, 1\n",
    "        while k < n and i < n and j < n:\n",
    "            if sec[(i + k) % n] == sec[(j + k) % n]:\n",
    "                k += 1\n",
    "            else:\n",
    "                if sec[(i + k) % n] < sec[(j + k) % n]:\n",
    "                    i = i + k + 1\n",
    "                else:\n",
    "                    j = j + k + 1\n",
    "                if i == j:\n",
    "                    i += 1\n",
    "                k = 0\n",
    "        i = i if i < j else j\n",
    "        return i, sec[i:] + sec[:i]\n",
    "\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        s += chr(ord(\"a\") - 1)\n",
    "        i, _ = LyndonDecomposition().max_express(s)\n",
    "        return s[i:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        b=list(set(s))\n",
    "        b.sort()\n",
    "        ch=b[-1]\n",
    "        idx=s.index(ch)\n",
    "        buff=[s[idx:], '']\n",
    "        while True:\n",
    "            idx=s.find(ch,idx+1)\n",
    "            buff[1]=s[idx:]\n",
    "            buff.sort(reverse=True)\n",
    "            if idx==-1:\n",
    "                break\n",
    "        return buff[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        ch = max(s)\n",
    "        res = ''\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == ch:\n",
    "               t = s[i:]\n",
    "               if t > res:\n",
    "                   res = t\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        #开头字典序最大的前提下, 尽可能长(空字符算作字典序最小)\n",
    "        curMax = 'a'\n",
    "        n = len(s)\n",
    "        for idx, c in enumerate(s[::-1]):\n",
    "            idx = n-idx-1\n",
    "            if c > curMax[0]:\n",
    "                curMax = s[idx:]\n",
    "            elif c == curMax[0]:\n",
    "                if curMax < s[idx:]:\n",
    "                    curMax = s[idx:]\n",
    "        return curMax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        ch = max(s)\n",
    "        res = ''\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == ch:\n",
    "               t = s[i:]\n",
    "               if t > res:\n",
    "                   res = t\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        maxC = max(s)\n",
    "        ans = ''\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == maxC:\n",
    "                t = s[i:]\n",
    "                if t > ans:\n",
    "                    ans = t\n",
    "        return ans\n",
    "\n",
    "    def lastSubstring2(self, s: str) -> str:\n",
    "        # 贪心，升序排在后面的肯定是相同字母并且长度最长的子字符串\n",
    "        return max(s[i:] for i in range(len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        su = []\n",
    "        last = ''\n",
    "        for i in range(len(s)):\n",
    "            if s[i] < last:\n",
    "                continue\n",
    "            if s[i] == last and (i ==0 or s[i-1]!=last):\n",
    "                su.append(i)\n",
    "            if s[i] > last:\n",
    "                last = s[i]\n",
    "                su = [i]\n",
    "        return max(s[e:] for e in su)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        maxn=max(list(s))\n",
    "        res=''\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==maxn:\n",
    "                res=max(res,s[i:])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        left,right,count,len1 = 0,1,1,len(s)\n",
    "        if len(set(list(s))) == 1:\n",
    "            return s\n",
    "        while right+count <= len1:\n",
    "            ## 当时s[left+count-1]较小时候，left:left+count中不可能成为最终起点\n",
    "            if s[left+count-1] < s[right+count-1]:\n",
    "                left += count\n",
    "                count = 1\n",
    "                if left >= right:\n",
    "                    right = left + 1\n",
    "            elif s[left+count-1] == s[right+count-1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                right += 1\n",
    "                count = 1\n",
    "        return s[left:]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        c=max(list(s))\n",
    "        ans=''\n",
    "        prev=''\n",
    "        for i,k in enumerate(s):\n",
    "            if k==prev:continue\n",
    "            if k==c:\n",
    "                if (ss:=s[i:])>ans:ans=ss\n",
    "            prev=k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        max_str = max(list(s))\n",
    "        res = \"\"\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == max_str:\n",
    "                if s[i:] > res:\n",
    "                    res= s[i:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        chars = list(s)\n",
    "        n = len(chars)\n",
    "        # Find the largest character c in string s\n",
    "        c = max(chars)\n",
    "        # Find the first occurrence of c in s\n",
    "        pos = chars.index(c)\n",
    "        # Set right to the next character after the first occurrence of c\n",
    "        right = pos + 1\n",
    "        # Loop through the remaining characters in s\n",
    "        while right < n:\n",
    "            # If the current character is not c, move to the next character\n",
    "            if chars[right] != c:\n",
    "                right += 1\n",
    "                continue\n",
    "            # Compare the two substrings starting at positions pos and right\n",
    "            i, j = pos + 1, right + 1\n",
    "            while j < n and chars[i] == chars[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            if j >= n:\n",
    "                break\n",
    "            # If the substring starting at 'right' is greater, update 'pos'\n",
    "            if chars[i] < chars[j]:\n",
    "                pos = right\n",
    "            # Move to the next character\n",
    "            right += 1\n",
    "        # Return the suffix starting at position 'pos'\n",
    "        return s[pos:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef lastSubstring(self, s):\n",
    "\t\tn, a, p = len(s), [False] * len(s), len(s) - 1\n",
    "\t\ta[p] = True\n",
    "\t\tfor i in range(n - 1, -1, -1):\n",
    "\t\t\tif s[i] < s[p]: continue\n",
    "\t\t\tif s[i] > s[p]:\n",
    "\t\t\t\tp = i\n",
    "\t\t\telse:\n",
    "\t\t\t\tok = True\n",
    "\t\t\t\tfor j in range(1, n - i):\n",
    "\t\t\t\t\tif p + j >= n or a[i + j] or s[i + j] > s[p + j]: break\n",
    "\t\t\t\t\tif s[i + j] < s[p + j]:\n",
    "\t\t\t\t\t\tok = False\n",
    "\t\t\t\t\t\tbreak\n",
    "\t\t\t\tif ok:\n",
    "\t\t\t\t\ta[i] = True\n",
    "\t\t\t\t\tp = i\n",
    "\t\treturn s[p:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "\n",
    "        ll = list(s)\n",
    "        z = sorted(list(set(ll)))[-1]\n",
    "        r = ''\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==z:\n",
    "                r = max(r, s[i:])\n",
    "        return r\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        s_list = list(s)\n",
    "        letters = list(set(s_list))\n",
    "        if letters == 1:\n",
    "            return s\n",
    "        letters.sort()\n",
    "        index = []\n",
    "        res = \"\"\n",
    "        for i, val in enumerate(s_list):\n",
    "            if val == letters[-1]:\n",
    "                if s[i:] > res:\n",
    "                    res = s[i:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        al=sorted(s)[-1]\n",
    "        ans=s\n",
    "        for i,ss in enumerate(s):\n",
    "            if ss==al:ans=max(ans,s[i:])\n",
    "        return ans    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        x=0;box=[0]*len(s)\n",
    "        for i,k in enumerate(s):\n",
    "            if ord(k)>x:\n",
    "                x=ord(k)\n",
    "        x=chr(x)\n",
    "        for i,k in enumerate(s):\n",
    "            if k==x:\n",
    "                box[i]=1\n",
    "        x=max(s[i:] for i in range(len(box)) if box[i]==1)\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        x=0;box=[0]*len(s)\n",
    "        for i,k in enumerate(s):\n",
    "            if ord(k)>x:\n",
    "                x=ord(k)\n",
    "        x=chr(x)\n",
    "        for i,k in enumerate(s):\n",
    "            if k==x:\n",
    "                box[i]=1\n",
    "        x=max(s[i:] for i in range(len(box)) if box[i]==1)\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        c = max(list(s))\n",
    "        return max(s[i:] for i, x in enumerate(s) if x == c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        c = max(list(s))\n",
    "        return max(s[i:] for i, x in enumerate(s) if x == c)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        l = [i for i in s]\n",
    "        l.sort()\n",
    "        maxChar = l[-1]\n",
    "        maxStr = \"\"\n",
    "        if not s:\n",
    "            return maxStr\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == maxChar:\n",
    "                maxStr = max(maxStr,s[i:])\n",
    "        return maxStr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def min_express(sec):\n",
    "    n = len(sec)\n",
    "    # Python Version\n",
    "    k, i, j = 0, 0, 1\n",
    "    while k < n and i < n and j < n:\n",
    "        if sec[(i + k) % n] == sec[(j + k) % n]:\n",
    "            k += 1\n",
    "        else:\n",
    "            if sec[(i + k) % n] > sec[(j + k) % n]:\n",
    "                i = i + k + 1\n",
    "            else:\n",
    "                j = j + k + 1\n",
    "            if i == j:\n",
    "                i += 1\n",
    "            k = 0\n",
    "    i = min(i, j)\n",
    "    return i\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        s += \"a\"\n",
    "        lst = [26-ord(w)+ord(\"a\") for w in s]\n",
    "        i = min_express(lst)\n",
    "        j = s.index(s[i:])\n",
    "        return s[j:][:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        ids = []\n",
    "        m = s[0]\n",
    "        for i in range(n):\n",
    "            if s[i] > m:\n",
    "                ids = [i]\n",
    "                m = s[i]\n",
    "            elif s[i] == m:\n",
    "                ids.append(i)\n",
    "        init = ids\n",
    "        ans = ids[0]\n",
    "        count = 0\n",
    "        while len(ids) > 1:\n",
    "            count += 1\n",
    "            ids = [i+1 for i in ids if i < n-1]\n",
    "            for i in range(len(ids)-2, -1, -1):\n",
    "                if ids[i] == ids[i+1] - count:\n",
    "                    del ids[i+1]\n",
    "            sl = [s[i] for i in ids]\n",
    "            ms = max(sl)\n",
    "            if sl.count(ms) == 1:\n",
    "                ans = ids[sl.index(ms)] - count\n",
    "            ni = []\n",
    "            for i in range(len(sl)):\n",
    "                if sl[i] == ms:\n",
    "                    ni.append(ids[i])\n",
    "            ids = ni\n",
    "        ans = ids[0] - count\n",
    "        return s[ans:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        s = s[::-1]\n",
    "        n = len(s)\n",
    "        dp = [0 for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            ii = i\n",
    "            j = dp[i-1]\n",
    "            while ii>dp[i-1] and j>=0 and s[ii] == s[j]:\n",
    "                ii -= 1\n",
    "                j -= 1\n",
    "            if j < 0 or ii == dp[i-1] or ord(s[ii])>ord(s[j]):\n",
    "                dp[i] = i\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        res = s[:dp[-1]+1][::-1]\n",
    "        return res\n",
    "        \n",
    "                \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LyndonDecomposition:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    # duval_algorithm\n",
    "    @staticmethod\n",
    "    def solve_by_duval(s):\n",
    "        n, i = len(s), 0\n",
    "        factorization = []\n",
    "        while i < n:\n",
    "            j, k = i + 1, i\n",
    "            while j < n and s[k] <= s[j]:\n",
    "                if s[k] < s[j]:\n",
    "                    k = i\n",
    "                else:\n",
    "                    k += 1\n",
    "                j += 1\n",
    "            while i <= k:\n",
    "                factorization.append(s[i: i + j - k])\n",
    "                i += j - k\n",
    "        return factorization\n",
    "\n",
    "    # smallest_cyclic_string\n",
    "    @staticmethod\n",
    "    def min_cyclic_string(s):\n",
    "        s += s\n",
    "        n = len(s)\n",
    "        i, ans = 0, 0\n",
    "        while i < n // 2:\n",
    "            ans = i\n",
    "            j, k = i + 1, i\n",
    "            while j < n and s[k] <= s[j]:\n",
    "                if s[k] < s[j]:\n",
    "                    k = i\n",
    "                else:\n",
    "                    k += 1\n",
    "                j += 1\n",
    "            while i <= k:\n",
    "                i += j - k\n",
    "        return s[ans: ans + n // 2]\n",
    "\n",
    "    @staticmethod\n",
    "    def min_express(sec):\n",
    "        n = len(sec)\n",
    "        k, i, j = 0, 0, 1\n",
    "        while k < n and i < n and j < n:\n",
    "            if sec[(i + k) % n] == sec[(j + k) % n]:\n",
    "                k += 1\n",
    "            else:\n",
    "                if sec[(i + k) % n] > sec[(j + k) % n]:\n",
    "                    i = i + k + 1\n",
    "                else:\n",
    "                    j = j + k + 1\n",
    "                if i == j:\n",
    "                    i += 1\n",
    "                k = 0\n",
    "        i = min(i, j)\n",
    "        return i\n",
    "\n",
    "    def max_express(self, sec):\n",
    "        # 这里用到一个小技巧，将求最大表示法的问题转换为求最小表示法\n",
    "        sec += \"a\"\n",
    "        lst = [26 - ord(w) + ord(\"a\") for w in sec]\n",
    "        i = self.min_express(lst)\n",
    "        # 注意最大来说要取第一个前缀的索引\n",
    "        return sec[i:][:-1] # 返回最大表示法的前半部分\n",
    "\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        return LyndonDecomposition().max_express(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        res=[]\n",
    "        for i in s:\n",
    "            res.append(ord(i)-ord('a')+1)\n",
    "        return max(s[i:] for i in range(len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Python Version\n",
    "def min_express(sec):\n",
    "    n = len(sec)\n",
    "    k, i, j = 0, 0, 1\n",
    "    while k < n and i < n and j < n:\n",
    "        if sec[(i + k) % n] == sec[(j + k) % n]:\n",
    "            k += 1\n",
    "        else:\n",
    "            if sec[(i + k) % n] > sec[(j + k) % n]:\n",
    "                i = i + k + 1\n",
    "            else:\n",
    "                j = j + k + 1\n",
    "            if i == j:\n",
    "                i += 1\n",
    "            k = 0\n",
    "    i = min(i, j)\n",
    "    return i\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        # 这里用到一个小技巧，将求最大表示法的问题转换为求最小表示法\n",
    "        s += \"a\"\n",
    "        lst = [26-ord(w)+ord(\"a\") for w in s]\n",
    "        i = min_express(lst)\n",
    "        # 注意最大来说要取第一个前缀的索引\n",
    "        j = s.index(s[i:])\n",
    "        return s[j:][:-1]\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/last-substring-in-lexicographical-order/solution/by-liupengsay-9c6e/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        s_len, left, right, step = len(s), 0, 1, 0\n",
    "        next_arr = [-1]\n",
    "        next_step = -1\n",
    "        while(right + step < s_len):\n",
    "            if s[right + step] > s[left + step]:\n",
    "                last_next_step = step - 1\n",
    "                next_step = next_arr[step - 1]\n",
    "                while next_step >= 0 and s[right + next_step + 1] < s[right + step]:\n",
    "                    last_next_step = next_step\n",
    "                    next_step = next_arr[last_next_step]\n",
    "                left = right + step - last_next_step - 1\n",
    "                right = left + 1\n",
    "                step = 0\n",
    "\n",
    "                next_step = -1\n",
    "                next_arr.clear()\n",
    "                next_arr.append(-1)\n",
    "            elif s[right + step] < s[left + step]:\n",
    "                right, step = right + step + 1, 0\n",
    "\n",
    "                next_step = -1\n",
    "                next_arr.clear()\n",
    "                next_arr.append(-1)\n",
    "            else:\n",
    "                step += 1\n",
    "                if right + step < s_len:\n",
    "                    while next_step >= 0 and s[right + next_step + 1] != s[right + step]:\n",
    "                        next_step = next_arr[next_step]\n",
    "                    \n",
    "                    if s[right + next_step + 1] == s[right + step]:\n",
    "                        next_step += 1\n",
    "                    \n",
    "                    next_arr.append(next_step)\n",
    "        return s[left:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        indexs, maxstr = [], 'a'\n",
    "        for i in range(len(s)):\n",
    "            if s[i] > maxstr:\n",
    "                indexs = [i]\n",
    "                maxstr = s[i]\n",
    "            elif s[i] == maxstr:\n",
    "                indexs.append(i)\n",
    "\n",
    "        r = s[indexs[0]:]\n",
    "        for i in range(1, len(indexs)):\n",
    "            if s[indexs[i]:] > r:\n",
    "                r = s[indexs[i]:]\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LyndonDecomposition:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    # duval_algorithm\n",
    "    @staticmethod\n",
    "    def solve_by_duval(s):\n",
    "        n, i = len(s), 0\n",
    "        factorization = []\n",
    "        while i < n:\n",
    "            j, k = i + 1, i\n",
    "            while j < n and s[k] <= s[j]:\n",
    "                if s[k] < s[j]:\n",
    "                    k = i\n",
    "                else:\n",
    "                    k += 1\n",
    "                j += 1\n",
    "            while i <= k:\n",
    "                factorization.append(s[i: i + j - k])\n",
    "                i += j - k\n",
    "        return factorization\n",
    "\n",
    "    # smallest_cyclic_string\n",
    "    @staticmethod\n",
    "    def min_cyclic_string(s):\n",
    "        s += s\n",
    "        n = len(s)\n",
    "        i, ans = 0, 0\n",
    "        while i < n // 2:\n",
    "            ans = i\n",
    "            j, k = i + 1, i\n",
    "            while j < n and s[k] <= s[j]:\n",
    "                if s[k] < s[j]:\n",
    "                    k = i\n",
    "                else:\n",
    "                    k += 1\n",
    "                j += 1\n",
    "            while i <= k:\n",
    "                i += j - k\n",
    "        return s[ans: ans + n // 2]\n",
    "\n",
    "    @staticmethod\n",
    "    def min_express(sec):\n",
    "        n = len(sec)\n",
    "        k, i, j = 0, 0, 1\n",
    "        while k < n and i < n and j < n:\n",
    "            if sec[(i + k) % n] == sec[(j + k) % n]:\n",
    "                k += 1\n",
    "            else:\n",
    "                if sec[(i + k) % n] > sec[(j + k) % n]:\n",
    "                    i = i + k + 1\n",
    "                else:\n",
    "                    j = j + k + 1\n",
    "                if i == j:\n",
    "                    i += 1\n",
    "                k = 0\n",
    "        i = min(i, j)\n",
    "        return i\n",
    "\n",
    "    def max_express(self, sec):\n",
    "        # 这里用到一个小技巧，将求最大表示法的问题转换为求最小表示法\n",
    "        sec += \"a\"\n",
    "        lst = [26 - ord(w) + ord(\"a\") for w in sec]\n",
    "        i = self.min_express(lst)\n",
    "        # 注意最大来说要取第一个前缀的索引\n",
    "        j = sec.index(sec[i:])\n",
    "        return sec[j:][:-1] # 返回最大表示法的前半部分\n",
    "\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        return LyndonDecomposition().max_express(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        pos = 0\n",
    "        chars = list(s)\n",
    "        n = len(chars)\n",
    "        for idx, ch in enumerate(chars[1:]):\n",
    "            if ch > chars[pos]:\n",
    "                # 注意下标是从1开始，错开一位，所以要加1\n",
    "                pos = idx + 1\n",
    "        \n",
    "        r = pos + 1\n",
    "        while r < n:\n",
    "            if chars[r] < chars[pos]:\n",
    "                r += 1\n",
    "                continue\n",
    "\n",
    "            # 遇到下一个和最大字母相同的值\n",
    "            j, k = pos + 1, r + 1\n",
    "            while j < r and k < n:\n",
    "                if chars[j] == chars[k]:\n",
    "                    j, k = j + 1, k + 1\n",
    "                elif chars[j] < chars[k]:\n",
    "                    pos = r\n",
    "                    r = k\n",
    "                    break\n",
    "                else:\n",
    "                    r = k\n",
    "                    break\n",
    "            \n",
    "            if j == r or k == n:\n",
    "                r = k\n",
    "\n",
    "        return s[pos:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        c = max(s)\n",
    "        pos = s.index(c)\n",
    "        right = pos + 1\n",
    "        \n",
    "        while right < n:\n",
    "            if s[right] != c:\n",
    "                right += 1\n",
    "                continue\n",
    "            i = pos + 1\n",
    "            j = right + 1\n",
    "            while j < n and s[i] == s[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            if j >= n:\n",
    "                break\n",
    "            if s[i] < s[j]:\n",
    "                pos = right\n",
    "            right += 1\n",
    "        return ''.join(s[pos:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        ret = []\n",
    "        for let in s:\n",
    "            if not ret:\n",
    "                ret.append(let)\n",
    "            else:\n",
    "                if ret[0] < let:\n",
    "                    ret = [let]\n",
    "                else:\n",
    "                    ret.append(let)\n",
    "        candidate = ''.join(ret)\n",
    "        \n",
    "        result = candidate\n",
    "        for i in range(0, len(candidate)-1):\n",
    "            if candidate[i] < candidate[0] and candidate[i+1] == candidate[0]:\n",
    "                result = max(result, candidate[i+1:])\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        letter = list(reversed(sorted(s)))[0]\n",
    "        msub = s\n",
    "        for i in range(len(s)):\n",
    "            tmp = s[i:]\n",
    "            if tmp > msub:\n",
    "                msub = tmp\n",
    "        return msub"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        s_set = set(s)\n",
    "        if len(s_set) == 1:\n",
    "            return s\n",
    "        max_s = max(s_set)\n",
    "        pos = []\n",
    "        if s[0] == max_s:\n",
    "            pos += [0]\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == max_s and s[i - 1] != max_s:\n",
    "                pos += [i]\n",
    "        n = len(pos)\n",
    "        res = pos[0]\n",
    "        pre = s[res:]\n",
    "        for i in range(1, n):\n",
    "            if i == n - 1:\n",
    "                cur = s[pos[i]:]\n",
    "            else:\n",
    "                cur = s[pos[i]:pos[i + 1]]\n",
    "            if cur > pre:\n",
    "                pre = cur\n",
    "                res = pos[i]\n",
    "        return s[res:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def lastSubstring(self, s: str) -> str:\n",
    "#         chrs = sorted(list(s))\n",
    "#         chr = chrs[-1]\n",
    "#         results = []\n",
    "#         for i, x in enumerate(s):\n",
    "#             if x == chr:\n",
    "#                 results.append(s[i:])\n",
    "#         results.sort()\n",
    "#         return results[-1]\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        chrs = sorted(list(s))\n",
    "        chr = chrs[-1]\n",
    "        result = s\n",
    "        for i, x in enumerate(s):\n",
    "            if x == chr and s[i:] > result:\n",
    "                result = s[i:]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LyndonDecomposition:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    # duval_algorithm\n",
    "    @staticmethod\n",
    "    def solve_by_duval(s):\n",
    "        n, i = len(s), 0\n",
    "        factorization = []\n",
    "        while i < n:\n",
    "            j, k = i + 1, i\n",
    "            while j < n and s[k] <= s[j]:\n",
    "                if s[k] < s[j]:\n",
    "                    k = i\n",
    "                else:\n",
    "                    k += 1\n",
    "                j += 1\n",
    "            while i <= k:\n",
    "                factorization.append(s[i: i + j - k])\n",
    "                i += j - k\n",
    "        return factorization\n",
    "\n",
    "    # smallest_cyclic_string\n",
    "    @staticmethod\n",
    "    def min_cyclic_string(s):\n",
    "        s += s\n",
    "        n = len(s)\n",
    "        i, ans = 0, 0\n",
    "        while i < n // 2:\n",
    "            ans = i\n",
    "            j, k = i + 1, i\n",
    "            while j < n and s[k] <= s[j]:\n",
    "                if s[k] < s[j]:\n",
    "                    k = i\n",
    "                else:\n",
    "                    k += 1\n",
    "                j += 1\n",
    "            while i <= k:\n",
    "                i += j - k\n",
    "        return s[ans: ans + n // 2]\n",
    "\n",
    "    @staticmethod\n",
    "    def min_express(sec):\n",
    "        n = len(sec)\n",
    "        k, i, j = 0, 0, 1\n",
    "        while k < n and i < n and j < n:\n",
    "            if sec[(i + k) % n] == sec[(j + k) % n]:\n",
    "                k += 1\n",
    "            else:\n",
    "                if sec[(i + k) % n] > sec[(j + k) % n]:\n",
    "                    i = i + k + 1\n",
    "                else:\n",
    "                    j = j + k + 1\n",
    "                if i == j:\n",
    "                    i += 1\n",
    "                k = 0\n",
    "        i = min(i, j)\n",
    "        return i\n",
    "\n",
    "    def max_express(self, sec):\n",
    "        # 这里用到一个小技巧，将求最大表示法的问题转换为求最小表示法\n",
    "        sec += chr(ord(\"a\")-1)\n",
    "        lst = [26 - ord(w) + ord(\"a\") for w in sec]\n",
    "        i = self.min_express(lst)\n",
    "        # 注意最大来说要取第一个前缀的索引\n",
    "        return sec[i:][:-1] # 返回最大表示法的前半部分\n",
    "\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        return LyndonDecomposition().max_express(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        Count = 0\n",
    "        MaxCount = 1\n",
    "        MaxStr = max(s)\n",
    "        lstStr = []\n",
    "        Flag = \"A\"\n",
    "        for i in range(len(s)):\n",
    "            if(s[i]==MaxStr):\n",
    "                if(s[i]==s[i-1]):\n",
    "                    Count += 1\n",
    "                else:\n",
    "                    Count = 1\n",
    "                continue\n",
    "            elif(Count >= MaxCount and s[i-1]==MaxStr):\n",
    "                if(Count == MaxCount and s[i]<Flag):\n",
    "                    continue\n",
    "                if(lstStr !=[] and (s[i-MaxCount:] == lstStr[-1][:len(s[i-MaxCount:])-len(lstStr[-1])])):\n",
    "                    break\n",
    "                MaxCount = Count\n",
    "                Count = 0\n",
    "                Flag = s[i]\n",
    "                lstStr.append(s[i-MaxCount:])\n",
    "        if(Count >= MaxCount):\n",
    "            MaxCount = Count\n",
    "            Count = 1\n",
    "            lstStr.append(s[i-MaxCount+1:])  \n",
    "        lstStr.sort()\n",
    "        return lstStr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        Count = 0\n",
    "        MaxCount = 1\n",
    "        MaxStr = max(s)\n",
    "        lstStr = []\n",
    "        for i in range(len(s)):\n",
    "            if(s[i]==MaxStr):\n",
    "                if(s[i]==s[i-1]):\n",
    "                    Count += 1\n",
    "                else:\n",
    "                    Count = 1\n",
    "                continue\n",
    "            elif(Count >= MaxCount and s[i-1]==MaxStr):\n",
    "                if(lstStr !=[] and (s[i-MaxCount:] == lstStr[-1][:len(s[i-MaxCount:])-len(lstStr[-1])])):\n",
    "                    break\n",
    "                MaxCount = Count\n",
    "                Count = 0\n",
    "                lstStr.append(s[i-MaxCount:])\n",
    "        if(Count >= MaxCount):\n",
    "            MaxCount = Count\n",
    "            Count = 1\n",
    "            lstStr.append(s[i-MaxCount+1:])  \n",
    "        return max(lstStr)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def cmp(i:int,j:int)->int: # cmp s[i:] , s[j:] ,assert i < j, if s[i:] > s[j:], return 1 else 0\n",
    "            if j == len(s):\n",
    "                return 1\n",
    "            if s[i] > s[j]:\n",
    "                return 1\n",
    "            if s[i] < s[j]:\n",
    "                return 0\n",
    "            return cmp(i+1,j+1)\n",
    "\n",
    "        char = max(s)\n",
    "        index = [idx for idx in range(len(s)) if s[idx] == char]\n",
    "        while len(index)>1:\n",
    "            mark = [1]*len(index)\n",
    "            for i in range(len(index)-2,-1,-1):\n",
    "                mark[i+cmp(index[i],index[i+1])] = 0\n",
    "            index = [index[i] for i in range(len(index)) if mark[i]==1]\n",
    "        result = index[0]\n",
    "        return s[result:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        arr = deque([0])\n",
    "        for i, ch in enumerate(s[1:], 1):\n",
    "            if ch > s[arr[0]]:\n",
    "                arr.clear()\n",
    "                arr = deque([i])\n",
    "            elif ch == s[arr[0]] and ch != s[i-1]:\n",
    "                arr.append(i)\n",
    "        # print(arr)\n",
    "        k = 0\n",
    "        n = len(s)\n",
    "        while len(arr) > 1:\n",
    "            k += 1\n",
    "            j = arr.popleft()\n",
    "            update = deque([j])\n",
    "            while arr:\n",
    "                i = arr.popleft()\n",
    "                if i + k < n and j + k < i:\n",
    "                    if s[j + k] < s[i + k]:\n",
    "                        update.clear()\n",
    "                        update.append(i)\n",
    "                        j = i\n",
    "                    elif s[j + k] == s[i + k]:\n",
    "                        update.append(i)\n",
    "                        j = i\n",
    "            arr = update\n",
    "            # print(arr)\n",
    "        return s[arr[0]:] \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        value = max(s)\n",
    "        index = [i for i in range(len(s)) if s[i] == value]\n",
    "        res = s[index[0]:]\n",
    "        for i in index:\n",
    "            res = max(res,s[i:])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        Count = 0\n",
    "        MaxCount = 1\n",
    "        MaxStr = max(s)\n",
    "        lstStr = []\n",
    "        for i in range(len(s)):\n",
    "            if(s[i]==MaxStr):\n",
    "                if(s[i]==s[i-1]):\n",
    "                    Count += 1\n",
    "                else:\n",
    "                    Count = 1\n",
    "                continue\n",
    "            elif(Count >= MaxCount and s[i-1]==MaxStr):\n",
    "                if(lstStr !=[] and (s[i-MaxCount:] == lstStr[-1][:len(s[i-MaxCount:])-len(lstStr[-1])])):\n",
    "                    break\n",
    "                MaxCount = Count\n",
    "                Count = 0\n",
    "                lstStr.append(s[i-MaxCount:])\n",
    "        if(Count >= MaxCount):\n",
    "            MaxCount = Count\n",
    "            Count = 1\n",
    "            lstStr.append(s[i-MaxCount+1:])  \n",
    "        lstStr.sort()\n",
    "        return lstStr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        length = len(s)\n",
    "        max_str = s[0]\n",
    "        max_str_index = [0]\n",
    "        for i in range(1, length):\n",
    "            if s[i] > max_str:\n",
    "                max_str = s[i]\n",
    "                max_str_index = [i]\n",
    "            elif s[i] == max_str:\n",
    "                max_str_index.append(i)\n",
    "        if len(max_str_index) == 1:\n",
    "            return s[max_str_index[0]:]\n",
    "\n",
    "        left = max_str_index[0]\n",
    "        right = max_str_index[1]\n",
    "        step = 0\n",
    "        while right+step < length:\n",
    "            if s[left + step] > s[right + step]:\n",
    "                right = right + step + 1\n",
    "                step = 0\n",
    "            elif s[left + step] < s[right + step]:\n",
    "                left = right\n",
    "                right += 1\n",
    "                step = 0\n",
    "            else:\n",
    "                step += 1\n",
    "        return s[left:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # class ListNode:\n",
    "    #     def __init__(self, start, end, next=None):\n",
    "    #         self.start = start\n",
    "    #         self.end = end\n",
    "    #         self.next = next\n",
    "    # class LinkedList:\n",
    "    #     def __init__(self, head=None):\n",
    "    #         self.head = head \n",
    "    #     def __repr__(self):\n",
    "    #         sb = ''\n",
    "    #         curNode = self.head\n",
    "    #         while curNode is not None:\n",
    "    #             sb += str(curNode.start) + \",\" + str(curNode.end) + \";\"\n",
    "    #             curNode = curNode.next\n",
    "    #         return sb\n",
    "\n",
    "    # def lastSubstring(self, s: str) -> str:\n",
    "    #     linkedList = self.LinkedList(head=self.ListNode(start=0,end=0))\n",
    "    #     for i in range(len(s)):\n",
    "    #         if s[i] > s[linkedList.head.start]:\n",
    "    #             linkedList.head = self.ListNode(start=i,end=i)\n",
    "    #         elif s[i] == s[linkedList.head.start]:\n",
    "    #             linkedList.head = self.ListNode(start=i,end=i,next=linkedList.head)\n",
    "\n",
    "    #     res = ''\n",
    "    #     while linkedList.head is not None:\n",
    "    #         curNode = linkedList.head\n",
    "    #         previousNode = None\n",
    "    #         maxChar = None\n",
    "    #         while curNode is not None:\n",
    "    #             if curNode.end == len(s)-1:\n",
    "    #                 res = s[curNode.start:curNode.end+1]\n",
    "    #                 linkedList.head = curNode.next\n",
    "    #                 curNode = curNode.next\n",
    "    #                 continue\n",
    "    #             c = s[curNode.end+1]\n",
    "    #             if maxChar is None or c > maxChar:\n",
    "    #                 curNode.end += 1\n",
    "    #                 linkedList.head = curNode\n",
    "    #                 maxChar = c\n",
    "    #                 previousNode = curNode\n",
    "    #             elif c == maxChar:\n",
    "    #                 curNode.end += 1\n",
    "    #             else:\n",
    "    #                 previousNode.next = curNode.next\n",
    "    #                 curNode = previousNode\n",
    "    #             previousNode = curNode\n",
    "    #             curNode = curNode.next\n",
    "    #     return res\n",
    "\n",
    "\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        start1 = 0\n",
    "        start2 = 0\n",
    "        starts = [0]\n",
    "        i = 1\n",
    "        while start2 + i < len(s):\n",
    "            # print(starts)\n",
    "            # print(s[start1:start1+i+1], s[start2:start2+i+1])\n",
    "            if s[start2+i] > s[start1]:\n",
    "                start2 += i\n",
    "                start1 = start2\n",
    "                i = 1\n",
    "                starts = [start2]\n",
    "                continue\n",
    "            if s[start1:start1+i+1] < s[start2:start2+i+1]:\n",
    "                del starts[0]\n",
    "                start1 = starts[0]\n",
    "                continue\n",
    "            if s[start2+i] == s[start1]:\n",
    "                start2 += i\n",
    "                i = 1\n",
    "                starts.append(start2)\n",
    "\n",
    "            if s[start1:start1+i+1] == s[start2:start2+i+1]:\n",
    "                i += 1\n",
    "                continue\n",
    "            if s[start1:start1+i+1] > s[start2:start2+i+1]:\n",
    "                starts.pop()\n",
    "                lastStart2 = starts[-1]\n",
    "                i = start2-lastStart2+i\n",
    "                start2 = lastStart2\n",
    "                continue\n",
    "        return s[start1:]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        Count = 0\n",
    "        MaxCount = 1\n",
    "        MaxStr = max(s)\n",
    "        lstStr = []\n",
    "        for i in range(len(s)):\n",
    "            if(s[i]==MaxStr):\n",
    "                if(s[i]==s[i-1]):\n",
    "                    Count += 1\n",
    "                else:\n",
    "                    Count = 1\n",
    "                continue\n",
    "            elif(Count >= MaxCount and s[i-1]==MaxStr):\n",
    "                if(lstStr !=[] and (s[i-MaxCount:] == lstStr[-1][:len(s[i-MaxCount:])-len(lstStr[-1])])):\n",
    "                    break\n",
    "                MaxCount = Count\n",
    "                Count = 0\n",
    "                lstStr.append(s[i-MaxCount:])\n",
    "        if(Count >= MaxCount):\n",
    "            MaxCount = Count\n",
    "            Count = 1\n",
    "            lstStr.append(s[i-MaxCount+1:])  \n",
    "        lstStr.sort()\n",
    "        return lstStr[-1]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def cmp(i:int,j:int)->int: # cmp s[i:] , s[j:] ,assert i < j, if s[i:] > s[j:], return 1 else 0\n",
    "            if j == len(s):\n",
    "                return 1\n",
    "            if s[i] > s[j]:\n",
    "                return 1\n",
    "            if s[i] < s[j]:\n",
    "                return 0\n",
    "            return cmp(i+1,j+1)\n",
    "\n",
    "        char = max(s)\n",
    "        index = [idx for idx in range(len(s)) if s[idx] == char]\n",
    "        while len(index)>1:\n",
    "            mark = [1]*len(index)\n",
    "            for i in range(len(index)-2,-1,-1):\n",
    "                mark[i+cmp(index[i],index[i+1])] = 0\n",
    "            index = [index[i] for i in range(len(index)) if mark[i]==1]\n",
    "        result = index[0]\n",
    "        return s[result:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        max_ch = s[0]\n",
    "        idxlist = [0]\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] > max_ch:\n",
    "                max_ch = s[i]\n",
    "                idxlist = [i]\n",
    "            elif s[i] == max_ch:\n",
    "                if idxlist and idxlist[-1] + 1 == i:\n",
    "                    continue\n",
    "                idxlist.append(i)\n",
    "        \n",
    "        res = ''\n",
    "        for i in idxlist:\n",
    "            res = max(res, s[i:])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        x='a'\n",
    "        for i in range(n):\n",
    "            x=max(x,s[i])\n",
    "        tmp=[]\n",
    "        for i in range(n):\n",
    "            if s[i]==x:\n",
    "                tmp.append(i)\n",
    "        if len(tmp)==1:\n",
    "            return s[tmp[0]:n]\n",
    "        res=0\n",
    "        cur=1\n",
    "        i=tmp[1]+1\n",
    "        while i<n:\n",
    "            t=i-tmp[cur]\n",
    "            if s[i]>s[tmp[res]+t]:\n",
    "                res=cur\n",
    "                cur+=1\n",
    "                if cur>=len(tmp):\n",
    "                    break\n",
    "                i=tmp[cur]\n",
    "            elif s[i]<s[tmp[res]+t]:\n",
    "                cur+=1\n",
    "                if cur>=len(tmp):\n",
    "                    break\n",
    "                i=tmp[cur]\n",
    "            i+=1\n",
    "        return s[tmp[res]:n]\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        t = max(s)\n",
    "        l = []\n",
    "        f = True\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == t:\n",
    "                if f:\n",
    "                    l.append(i)\n",
    "                f = False\n",
    "            else:\n",
    "                f = True\n",
    "        return max(s[i:] for i in l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        ks = set(s)\n",
    "        if len(ks) <= 1:\n",
    "            return s\n",
    "        k = max(ks)\n",
    "        re = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == k:\n",
    "                if i > 0 and s[i-1] == k:\n",
    "                    continue\n",
    "                re.append(i)\n",
    "        re = max(s[i:] for i in re)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        Count = 0\n",
    "        MaxCount = 1\n",
    "        MaxStr = max(s)\n",
    "        lstStr = []\n",
    "        for i in range(len(s)):\n",
    "            if(s[i]==MaxStr):\n",
    "                if(s[i]==s[i-1]):\n",
    "                    Count += 1\n",
    "                else:\n",
    "                    Count = 1\n",
    "                continue\n",
    "            elif(Count >= MaxCount and s[i-1]==MaxStr):\n",
    "                if(lstStr !=[] and (s[i-MaxCount:] == lstStr[-1][:len(s[i-MaxCount:])-len(lstStr[-1])])):\n",
    "                    break\n",
    "                MaxCount = Count\n",
    "                Count = 0\n",
    "                lstStr.append(s[i-MaxCount:])\n",
    "        if(Count >= MaxCount):\n",
    "            MaxCount = Count\n",
    "            Count = 1\n",
    "            lstStr.append(s[i-MaxCount+1:])  \n",
    "        return max(lstStr)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def cmp(i:int,j:int)->int: # cmp s[i:] , s[j:] ,assert i < j, if s[i:] > s[j:], return 1 else 0\n",
    "            if j == len(s):\n",
    "                return 1\n",
    "            if s[i] > s[j]:\n",
    "                return 1\n",
    "            if s[i] < s[j]:\n",
    "                return 0\n",
    "            return cmp(i+1,j+1)\n",
    "\n",
    "        char = max(s)\n",
    "        index = [idx for idx in range(len(s)) if s[idx] == char]\n",
    "        while len(index)>1:\n",
    "            mark = [1]*len(index)\n",
    "            for i in range(len(index)-2,-1,-1):\n",
    "                mark[i+cmp(index[i],index[i+1])] = 0\n",
    "            index = [index[i] for i in range(len(index)) if mark[i]==1]\n",
    "        result = index[0]\n",
    "        return s[result:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        max_char = 'a'\n",
    "        iml = []\n",
    "        for idx,val in enumerate(s):\n",
    "            if val > max_char: \n",
    "                max_char = val\n",
    "                iml = [idx]\n",
    "            elif val == max_char:\n",
    "                iml.append(idx)\n",
    "            \n",
    "        return max((s[iml[i]:] for i in range(len(iml))))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        tmax = max(ord(char) for char in s)\n",
    "        inds = [i for i in range(len(s)) if ord(s[i]) == tmax]\n",
    "        if len(inds) == 1:\n",
    "            return s[inds[0]:]\n",
    "        elif len(inds) == len(s):\n",
    "            return s\n",
    "        \n",
    "        ans = s[inds[0]:]\n",
    "        inds.pop(0)\n",
    "        for i in inds:\n",
    "            if s[i:] > ans:\n",
    "                ans = s[i:]\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        max_ = 0\n",
    "        index = -1\n",
    "        for i in range(len(s)):\n",
    "           if ord(s[i]) - ord('a') > max_:\n",
    "               index = i\n",
    "               max_ = ord(s[i]) - ord('a')\n",
    "        index_list = []\n",
    "        for i in range(len(s)):\n",
    "            if i>0:\n",
    "                if s[i] == s[index] and s[i-1] != s[index]:\n",
    "                    index_list.append(i)\n",
    "            else:\n",
    "                if s[i] == s[index]:\n",
    "                    index_list.append(i)\n",
    "        contract = s[index_list[-1]:]\n",
    "        index_res = index_list[-1]\n",
    "       \n",
    "        for i in range(len(index_list)-2,-1,-1):\n",
    "            len_ = min(len(contract),index_list[i+1] - index_list[i])\n",
    "            count_ = 0\n",
    "            flag = False\n",
    "            while count_ < len_:\n",
    "                \n",
    "                if s[index_list[i]+count_] > contract[count_]:\n",
    "                    contract = s[index_list[i]:]\n",
    "                    flag = True\n",
    "                    index_res = index_list[i]\n",
    "                    break\n",
    "                elif s[index_list[i]+count_] < contract[count_]:\n",
    "                    flag = True\n",
    "                \n",
    "                    break\n",
    "                count_ += 1\n",
    "            if not flag:\n",
    "                contract = s[index_list[i]:]\n",
    "                index_res = index_list[i]\n",
    "            \n",
    "        return s[index_res:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, origin_str: str) -> str:\n",
    "        if origin_str == origin_str[0] * len(origin_str):\n",
    "            return origin_str\n",
    "        max_char, index_list = 'a', []\n",
    "        for i in range(len(origin_str)):\n",
    "            if ord(origin_str[i]) > ord(max_char):\n",
    "                max_char, index_list = origin_str[i], [i]\n",
    "            elif ord(origin_str[i]) == ord(max_char):\n",
    "                index_list.append((i))\n",
    "            else:\n",
    "                continue\n",
    "        return max(origin_str[i:] for i in index_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, origin_str: str) -> str:\n",
    "        if origin_str == origin_str[0] * len(origin_str):\n",
    "            return origin_str\n",
    "        max_char, index_list = 'a', []\n",
    "        for i in range(len(origin_str)):\n",
    "            if ord(origin_str[i]) > ord(max_char):\n",
    "                max_char, index_list = origin_str[i], [i]\n",
    "            elif ord(origin_str[i]) == ord(max_char):\n",
    "                index_list.append((i))\n",
    "            else:\n",
    "                continue\n",
    "        return max(origin_str[i:] for i in index_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        max_s = max(s)\n",
    "\n",
    "        idx = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == max_s:\n",
    "                idx.append(i)\n",
    "        maxsub = s[idx[0]:]\n",
    "        for i in idx:\n",
    "            if s[i:] > maxsub:\n",
    "                maxsub = s[i:]\n",
    "\n",
    "\n",
    "        return maxsub"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        alphas=set(s)\n",
    "        alpha=[]\n",
    "        for c in alphas:\n",
    "            alpha.append(c)\n",
    "        alpha.sort(key=lambda x:ord(x))\n",
    "        if len(alpha)==1:\n",
    "            return s\n",
    "        targetidx=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==alpha[-1]:\n",
    "                targetidx.append(i)\n",
    "\n",
    "        ans=targetidx[-1]\n",
    "        if len(targetidx)==1:\n",
    "            return s[ans:]\n",
    "        for i in range(len(targetidx)-2,-1,-1):\n",
    "            idx=targetidx[i]\n",
    "            falg=True\n",
    "            for lenth in range(1,ans-idx):\n",
    "                if ans+lenth>=len(s) or s[idx+lenth]>s[ans+lenth]:\n",
    "                    break\n",
    "                if s[idx+lenth]<s[ans+lenth]:\n",
    "                    falg=False\n",
    "                    break\n",
    "            if falg:\n",
    "                ans=idx\n",
    "        return s[ans:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        alphas=set(s)\n",
    "        alpha=[]\n",
    "        for c in alphas:\n",
    "            alpha.append(c)\n",
    "        alpha.sort(key=lambda x:ord(x))\n",
    "        if len(alpha)==1:\n",
    "            return s\n",
    "        targetidx=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==alpha[-1]:\n",
    "                targetidx.append(i)\n",
    "        #targetidx=maps[alpha[-1]]\n",
    "        ans=targetidx[-1]\n",
    "        if len(targetidx)==1:\n",
    "            return s[ans:]\n",
    "        for i in range(len(targetidx)-2,-1,-1):\n",
    "            idx=targetidx[i]\n",
    "            falg=True\n",
    "            for lenth in range(1,ans-idx):\n",
    "                if ans+lenth>=len(s) or s[idx+lenth]>s[ans+lenth]:\n",
    "                    break\n",
    "                if s[idx+lenth]<s[ans+lenth]:\n",
    "                    falg=False\n",
    "                    break\n",
    "            if falg:\n",
    "                ans=idx\n",
    "        return s[ans:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        l = len(s)\n",
    "        m = chr(ord('a') - 1)\n",
    "        num = []\n",
    "        ans = 'a'\n",
    "        for a in range(l):\n",
    "            if s[a] > m:\n",
    "                m = s[a]\n",
    "                num.clear()\n",
    "                num.append(a)\n",
    "            elif s[a] == m:\n",
    "                num.append(a)\n",
    "        L = len(num)\n",
    "        for a in range(L):\n",
    "            str_ = s[num[a]:l]\n",
    "            if ans < str_:\n",
    "                ans = str_\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        mc = s[0]\n",
    "        ml = 1\n",
    "        pl = 0\n",
    "        for c in s:\n",
    "            if c > mc:\n",
    "                mc = c\n",
    "                pl = ml = 1\n",
    "            elif c == mc:\n",
    "                pl += 1\n",
    "            else:\n",
    "                if pl > ml:\n",
    "                    ml = pl\n",
    "                pl = 0\n",
    "        l = []\n",
    "        pl = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == mc:\n",
    "                pl += 1\n",
    "                if pl == ml:\n",
    "                    l.append(i)\n",
    "            else:\n",
    "                pl = 0\n",
    "        d = 1\n",
    "        while len(l) > 1 and l[0] + d < n:\n",
    "            l1 = []\n",
    "            cm = s[l[0] + d]\n",
    "            for i in l:\n",
    "                if i + d >= n:\n",
    "                    break\n",
    "                if s[i + d] < cm:\n",
    "                    continue\n",
    "                if s[i + d] > cm:\n",
    "                    cm = s[i + d]\n",
    "                    l1 = []\n",
    "                l1.append(i)\n",
    "            l = l1\n",
    "            d += 1\n",
    "            if cm == mc:\n",
    "                break\n",
    "        return s[l[0] - ml + 1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        l=len(s)\n",
    "        dp=[0]*l\n",
    "        j=0\n",
    "        d=['a']*5\n",
    "        res = \"\"\n",
    "        for i in range(l):\n",
    "            if s[i]>d[0]:\n",
    "                d[0]=s[i]\n",
    "                dp[0]=i\n",
    "                j=1\n",
    "                if i+1<l:\n",
    "                    d[1]=s[i+1]\n",
    "            elif s[i]==d[0]:\n",
    "                if i+1==l:\n",
    "                    dp[j]==i\n",
    "                    j=j+1\n",
    "                    break\n",
    "                if s[i+1]==d[1]:\n",
    "                    dp[j]=i\n",
    "                    j=j+1\n",
    "                elif s[i+1]>d[1]:\n",
    "                    d[1]=s[i+1]\n",
    "                    dp[0]=i\n",
    "                    j=1\n",
    "        for i in range(j):\n",
    "            res = max(res,s[dp[i]:])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        ls = [match.start() for match in re.finditer(max(s), s)]\n",
    "        result = s[ls[0]:]\n",
    "        for i in ls:\n",
    "            result = max(result, s[i:])\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        max_c = max(s)\n",
    "        prefix_len = s.index(max_c)\n",
    "        ss = s\n",
    "\n",
    "        s = bytearray(s.encode())\n",
    "        s = s[prefix_len:]\n",
    "        max_c = s[0]\n",
    "\n",
    "        prev_max_pos = [0]\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == max_c and s[i-1] != max_c:\n",
    "                prev_max_pos.append(i)\n",
    "            else:\n",
    "                prev_max_pos.append(prev_max_pos[-1])\n",
    "\n",
    "        i, j = 0, 0\n",
    "        n = 1\n",
    "        m = 0\n",
    "        for k in range(1, len(s)):\n",
    "            c = s[k]\n",
    "            if c > s[i + m]:\n",
    "                if prev_max_pos[k] != k-m and s[prev_max_pos[k]:k+1] > s[k-m:k+1]:\n",
    "                    i = prev_max_pos[k]\n",
    "                else:\n",
    "                    i = k-m\n",
    "                j = k\n",
    "                n = 1\n",
    "                m = 0\n",
    "            elif c == s[i + m]:\n",
    "                m += 1\n",
    "                if m == j - i + 1:\n",
    "                    m = 0\n",
    "                    n += 1\n",
    "            else:\n",
    "                i = i\n",
    "                j = k\n",
    "                m = 0\n",
    "                n = 1\n",
    "            # print(s, c, i, j, s[i:j+1], n, m)\n",
    "        return ss[prefix_len + i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        maxC, maxIdx = s[0], [0]\n",
    "        for i in range(1, n):\n",
    "            if s[i] > maxC:\n",
    "                maxC = s[i]\n",
    "                maxIdx = [i]\n",
    "            elif s[i] == maxC:\n",
    "                maxIdx.append(i)\n",
    "\n",
    "        ans = ''\n",
    "        for j in maxIdx:\n",
    "            ans = max(ans, s[j:])\n",
    "        \n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastSubstring(self, s: str) -> str:\n",
    "        b=list(set(s))\n",
    "        b.sort()\n",
    "        ch=b[-1]\n",
    "        tmps=[i for i,c in enumerate(s) if c==ch]\n",
    "        idx=s.index(ch)\n",
    "        buff=[s[idx:], '']\n",
    "        for idx in tmps:\n",
    "            buff[1]=s[idx:]\n",
    "            buff.sort(reverse=True)\n",
    "            if idx==-1:\n",
    "                break\n",
    "        return buff[0]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
